package com.wwg.algorithm_data_structures;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @类描述: TODO
 * @Author wwg
 * @date: 2022-04-03 19:54
 * @Version: 1.0
 **/
public class CombinationSum {

    public static void main(String[] args) {
        List<List<Integer>> lists = new CombinationSum().combinationSum(Arrays.asList(1,2, 3, 6, 7), 7);
        System.out.println(lists);
    }

    /**
     * @类描述: [2, 3, 7]  7
     * @Author wwg
     * @Date: 2022-04-03 20:06
     * @Params [candidates, target]
     * @Return java.util.List<java.util.List < java.lang.Integer>>
     */
    List<List<Integer>> combinationSum(List<Integer> candidates, int target) {

        ArrayList<List<Integer>> resultList = new ArrayList<>();

        ArrayList<ArrayList<ArrayList<Integer>>> splitLists = getSplitLists(candidates, target);
        List<LinkedHashMap<ArrayList<Integer>, Integer>> listSumValueMapList = listSumValueMapList(splitLists);

        for (int i = 0; i < listSumValueMapList.size(); i++) {
            LinkedHashMap<ArrayList<Integer>, Integer> linkedHashMap = listSumValueMapList.get(i);
            Set<ArrayList<Integer>> arrayLists = linkedHashMap.keySet();
            for (ArrayList<Integer> arrayList : arrayLists) {
                if (listSumValueMapList.size() - 1 > i) {
                    LinkedHashMap<ArrayList<Integer>, Integer> nextLinkedMap = listSumValueMapList.get(i + 1);
                    for (int i1 = 0; i1 < nextLinkedMap.size(); i1++) {
                        // 定义最终你那个结果集
                        ArrayList<Integer> resultCalcArray = new ArrayList<>();
                        // i+1 和下一个 map中的值遍历相加
                        Integer integer = linkedHashMap.get(arrayList);
                        resultCalcArray.addAll(arrayList);
                        extracted(target, resultList, listSumValueMapList, i + 1, i1, resultCalcArray, integer);
                    }
                }else {
                    // 定义最终你那个结果集
                    ArrayList<Integer> resultCalcArray = new ArrayList<>();
                    // i+1 和下一个 map中的值遍历相加
                    Integer integer = linkedHashMap.get(arrayList);
                    resultCalcArray.addAll(arrayList);

                    extracted(target, resultList, listSumValueMapList, -1, 0, resultCalcArray, integer);
                }


            }


        }

        return resultList;
    }

    private void extracted(int target, ArrayList<List<Integer>> resultList, List<LinkedHashMap<ArrayList<Integer>, Integer>> listSumValueMapList, int i,
                           int arrayListsCopyIndex,
                           ArrayList<Integer> resultCalcArray, Integer integer) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        Set<ArrayList<Integer>> arrayLists = null;
        if (-1 != i) {
            LinkedHashMap<ArrayList<Integer>, Integer> linkedHashMap = listSumValueMapList.get(i);
            arrayLists = linkedHashMap.keySet();
            //获取当前迭代的 map
            List<ArrayList<Integer>> arrayListsCopy = new ArrayList<>();
            arrayLists.stream().forEach(s -> arrayListsCopy.add(s));
    //        for (ArrayList<Integer> arrayList : arrayLists) {
             arrayList = arrayListsCopy.get(arrayListsCopyIndex);
            integer += linkedHashMap.get(arrayList);
        }
        // 单个值结果为target
        if (integer == target) {
            resultCalcArray.addAll(arrayList);
            resultList.add(resultCalcArray);
            System.out.println(resultList);
        } else if (integer < target) {
            // 将值传到下一个 map 的第一个list进行相加
            if (listSumValueMapList.size() - 1 > i && arrayLists.size() - 1 > arrayListsCopyIndex) {
                resultCalcArray.addAll(arrayList);
                extracted(target, resultList, listSumValueMapList, i + 1, 0, resultCalcArray, integer);
            } /*else if (listSumValueMapList.size() - 1 > i) {
                resultCalcArray.addAll(arrayList);
                extracted(target, resultList, listSumValueMapList, i, 1, resultCalcArray, integer);
            }*/
        }else {
//            相加超出target
        }

//        }
    }

    private List<LinkedHashMap<ArrayList<Integer>, Integer>> listSumValueMapList(ArrayList<ArrayList<ArrayList<Integer>>> splitLists) {
        List<LinkedHashMap<ArrayList<Integer>, Integer>> listSumValueMapList = new ArrayList<>();

        for (ArrayList<ArrayList<Integer>> splitList : splitLists) {
            LinkedHashMap<ArrayList<Integer>, Integer> listSumValueMap = new LinkedHashMap<>();
            for (int i = 0; i < splitList.size(); i++) {
                ArrayList<Integer> integers = splitList.get(i);
                listSumValueMap.put(integers, integers.stream().collect(Collectors.summingInt(s -> s)));
            }
            listSumValueMapList.add(listSumValueMap);
        }

        System.out.println(listSumValueMapList);

        return listSumValueMapList;
    }

    /**
     * @类描述: 获取单值组合
     * @Author wwg
     * @Date: 2022-04-03 21:10
     * @Params [candidates, target]
     * @Return java.util.ArrayList<java.util.ArrayList < java.util.ArrayList < java.lang.Integer>>>
     */
    private ArrayList<ArrayList<ArrayList<Integer>>> getSplitLists(List<Integer> candidates, int target) {
        /**
         * 2
         * 2 2
         * 2 2 2
         * 2 2 2 2  结束
         *
         * 3
         * 3 3
         * 3 3 3 结束
         *
         * 7
         * 7 7 结束
         */

        ArrayList<ArrayList<ArrayList<Integer>>> candidateSplitList = new ArrayList<>();

        for (int i = 0; i < candidates.size(); i++) {
            Integer candidate = candidates.get(i);
            ArrayList<ArrayList<Integer>> singleCandidateList = new ArrayList<>();
            ArrayList<Integer> list = new ArrayList<>();
            int sum = candidate;
            while (sum <= target) {
                list.add(candidate);
//                ArrayList<Integer> objects = new ArrayList<>(list.size());
                ArrayList<Integer> objects = new ArrayList<>();
                objects.addAll(list);
                singleCandidateList.add(objects);
                sum += candidate;

            }
            if (singleCandidateList.size() > 0) {
                candidateSplitList.add(singleCandidateList);
            }
        }
        System.out.println(candidateSplitList);

        return candidateSplitList;

    }
}
